import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SearchMain {
        
        private static long startTime;
        private static long stopTime;
        private static final int ITERATIONS = 1000;
        private static final int ARRAY_SIZE = 500000;
        
        static Integer[] ints;
        static List<Comparable> intsList = new ArrayList<Comparable>();
        private static long n;
        public static void main(String args[])
        throws IOException
        {
        	/*initialize();
        	MaxHeap maxHeap = new MaxHeap(ints);
        	HeapView heapView = new HeapView(maxHeap);
        	System.out.println(maxHeap.toString());
        	BufferedReader readCon = new BufferedReader(new InputStreamReader(System.in)); 
        	int in = Integer.parseInt(readCon.readLine());
        	while(in != -1)
        	{
        		int startIndex = in * 2;
        		System.out.println(ints[in] + "\n" + ints[startIndex + 1] +" " + ints[startIndex + 2]);
        		in = Integer.parseInt(readCon.readLine());
        	}
        	//linearSearch();*/
        	
        	initialize();
        	insertionSort();
        	initialize();
        	selectionSort();
        	initialize();
        	startTime = System.currentTimeMillis();
        	intsList = mergeSort(intsList);
        	for(int i = 0; i < ints.length; i++)
        		ints[i] = (Integer) intsList.get(i);
        	System.out.println("Merge Sort completed in " + (System.currentTimeMillis() - startTime) + " milliseconds.");
        	/*binarySearch();
        	linearSearch();*/
        	
        }
        public static void linearSearch()
        {
            LinearSearch lSearch = new LinearSearch(ints);
            startTime = System.currentTimeMillis();
            for(int i = 0; i < ITERATIONS; i++)
            {
                    n += lSearch.search((int)(Math.random() * ARRAY_SIZE));
            }
            stopTime = System.currentTimeMillis();
            System.out.println("Linear searches completed in " + (stopTime - startTime) + " milliseconds." + "\n" + "Average of " + n / ITERATIONS + " comparisons.");
        }
        public static void binarySearch()
        {
        	BinarySearch bSearch = new BinarySearch(ints);
        	startTime = System.currentTimeMillis();
            for(int i = 0; i < ITERATIONS; i++)
            {
                    n += bSearch.search((int)(Math.random() * ARRAY_SIZE));
            }
            stopTime = System.currentTimeMillis();
            System.out.println("Binary searches completed in " + (stopTime - startTime) + " milliseconds." + "\n" + "Average of " + n / ITERATIONS + " comparisons.");
        	
        }
        private static void initialize()
        {
        	intsList.clear();
        	ints = new Integer[ARRAY_SIZE];
            for(int i = 0; i < ints.length; i++)
            {
            	ints[i] = (int) (Math.random() * ARRAY_SIZE);
            }
            intsList.addAll(Arrays.asList(ints));
        }
        private static void selectionSort()
        {
        	long time = System.currentTimeMillis();
        	long comparisons = 0;
        	long moves = 0;
        	for(int i = 0; i < ints.length; i++)
        	{
        		Integer min = ints[i];
        		int minIndex = i;
        		for(int j = i; j <ints.length; j++)
        		{
        			comparisons++;
        			if(min.compareTo(ints[j]) > 0)
        			{
        				
        				min = ints[j];
        				minIndex = j;
        			}
        		}
        		Integer temp = ints[i];
        		ints[i] = min;
        		ints[minIndex] = temp;
        	}
        	System.out.println("Selection sort completed in " + (System.currentTimeMillis() - time) + " milliseconds.");
        }
        private static void insertionSort()
        {
        	startTime = System.currentTimeMillis();
        	for(int i = 0; i < ints.length; i++)
        	{
        		int min = ints[i];
        		int minIndex = i;
        		for(int j = i; j < ints.length; j++)
        		{
        			if(ints[j] < min)
        			{	
        				minIndex = j;
        				min = ints[j];
        			}
        		}
        		int temp = ints[minIndex];
        		ints[minIndex] = ints[i];
        		ints[i] = temp;
        	}
        	System.out.println("Insertion sort completed in " + (System.currentTimeMillis() - startTime) + " milliseconds.");
        }
        private static List<Comparable> mergeSort(List<Comparable> arrList)
        {
        	if(arrList.size() <= 1)
        		return arrList;
        	
        	List<Comparable> arrList1 = new ArrayList<Comparable>();
        	List<Comparable> arrList2 = new ArrayList<Comparable>();
        	arrList1.addAll(arrList.subList(0, arrList.size() / 2));
        	arrList2.addAll(arrList.subList(arrList.size() / 2, arrList.size()));
        	
        	return combine(mergeSort(arrList1), mergeSort(arrList2));
        	
        	
        	
        }
        private static List<Comparable> combine(List<Comparable> a, List<Comparable> b)
        {
        	List<Comparable> combined = new ArrayList<Comparable>();
        	while(a.size() > 0 && b.size() > 0)
        	{
        		if(a.get(0).compareTo(b.get(0)) > 0)
        			combined.add(b.remove(0));
        		else
        			combined.add(a.remove(0));
        	}
        	int aSize = a.size();
        	for(int i = 0; i < aSize; i++)
        		combined.add(a.remove(0));
        	int bSize = b.size();
        	for(int i = 0; i < bSize; i++)
        		combined.add(b.remove(0));
        	return combined;
        }
}
